package algo

// SelectSort 选择排序 O(N^2)
// 过程：遍历数组选择最小的数排到前面
// 0到n-1范围有序，为啥到n-1不是到n，因为到n-1的时候和最后的n比较完成后，就是有序的了
func SelectSort(arr []int) {
	l := len(arr)
	if l < 2 {
		return
	}

	for i := 0; i < l-1; i++ {
		min := i

		for j := i + 1; j < l; j++ {
			if arr[j] < arr[min] {
				min = j
			}
		}

		arr[i], arr[min] = arr[min], arr[i]

	}

}

// BubbleSort 冒泡排序  O(N^2)
// 过程：通过遍历将大数交互到后面，第一次0～N-1范围将大数冒泡到最右边，第二次0~N-2冒泡到最右边
func BubbleSort(arr []int) {
	l := len(arr)
	if l < 2 {
		return
	}

	for i := l - 1; i > 0; i-- {
		for j := 0; j < i; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}

}

// XOROne 一个数组中，一个数出现奇数次，其它都是偶数次，找出这个出现奇数次的数
// XOR 两个数相同，做异或运算结果为0
func XOROne(arr []int) int {
	ero := 0
	for i := 0; i < len(arr); i++ {
		ero ^= arr[i]
	}

	return ero
}

// XORTow 一个数组中，两个数出现奇数次，其它都是偶数，找出这两个出现奇数次的数
func XORTow(arr []int) (a, b int) {
	eor := 0
	for i := 0; i < len(arr); i++ {
		eor ^= arr[i]
	}

	// eor= a^b
	// eor!=0  因为两个数不相同
	// 由于eor ！=0 ，所以二进制上有一位为1
	// 找出第一个bit位为1的数
	onlyOne := eor & (^eor + 1)
	firstOne := 0 //类似eor 用于找出a或b 其中一个
	for i := 0; i < len(arr); i++ {
		//分组，目的是把a,b分开
		if onlyOne&arr[i] == 0 {
			firstOne ^= arr[i]
		}
	}

	a = firstOne
	b = firstOne ^ eor
	return
}

// InsertSort 插入排序 O(N^2)
// 过程：保证当前数列有序的情况，将下一个数列插入到当前合适的位置，像摸牌的时候一样
// 与选择和冒泡不同，插入排序的时间和样本的排序情况有关，样本越有序，时间越少，因为只有比较，不用交换
func InsertSort(arr []int) {
	l := len(arr)
	if l < 2 {
		return
	}

	for i := 0; i < l; i++ {
		for j := i; j > 0; j-- {
			if arr[j] < arr[j-1] {
				arr[j], arr[j-1] = arr[j-1], arr[j]
			} else {
				//原有数据有序，不用比较完成直接跳过
				break
			}
		}
	}
}
